package progect_01;

import java.util.ArrayList;

public class CreAVLTree {
	public static void main(String[] args) {

		int[] arr = {10,11,7,6,8,9};
		ArrayList<TreeNode> list = new ArrayList<>();
		for (int i = 0; i < arr.length; i++) {
			list.add(new TreeNode(arr[i]));
		}
		AVLTree rooTree = new AVLTree(list.get(0));
		for (int i = 1; i < list.size(); i++) {
			rooTree.CreBinarySortTree(list.get(i));
		}
		// 前序遍历
		rooTree.PreOrderPrint();
		System.out.println();
	}

}

class AVLTree {
	private TreeNode rootNode;

	public AVLTree(TreeNode rootNode) {
		this.rootNode = rootNode;
	}

	// 获取根节点
	public TreeNode getRootNode() {
		return rootNode;
	}

	// 前序遍历
	public void PreOrderPrint() {
		if (rootNode == null) {
			return;
		} else {
			rootNode.PreOrder();
		}
	}

	// 创建二叉排序树
	public void CreBinarySortTree(TreeNode node) {
		if (rootNode == null) {
			rootNode = node;
		} else {
			rootNode.add(node);
		}
		

	}

}

class TreeNode {
	private int data;
	private TreeNode leftNode;
	private TreeNode rightNode;

	// 前序遍历
	public void PreOrder() {
		System.out.print(this.getData() + " ");
		if (this.leftNode != null) {
			this.leftNode.PreOrder();
		}
		if (this.rightNode != null) {
			this.rightNode.PreOrder();
		}

	}

	// 右旋---》当前节点的左子树的左子树的高度 > 当前节点左子树的右子树的高度
	//    ====》并且 当前节点的左子树的高度是 - 当前节点右子树的高度的>1
	
	public void RRrotate() {
		// 新节点的值放当前节点的值
		TreeNode NewRoot = new TreeNode(data);
		// 新节点的右子树等于当前节点的右子树
		NewRoot.rightNode = rightNode;
		// 新节点的左子树等于当前节点的左子树的右子树
		NewRoot.leftNode = leftNode.rightNode;
		// 当前节点的值设置为当前节点的左子树的值
		setData(leftNode.data);
		// 当前节点的左子树连当前节点的左子树的左子树
		leftNode = leftNode.leftNode;
		// 当前节点的右子树连新节点
		rightNode = NewRoot;
	}
	
	
	//先左旋再右旋-当前节点的左子树的右子树的高度 > 当前节点左子树的左子树的高度
//  ====》并且 当前节点的左子树的高度是 - 当前节点右子树的高度的>1
	public void LRrotate(){
		this.leftNode.LLrotate();//当前节点的 以左子节点为根节点先左旋
		this.RRrotate();//当前节点右旋
	}
	

	// 左旋---》当前节点右子树的右子树的高度 > 当前节点右子树的左子树的高度(注意)
//  ====》并且 当前节点的右子树的高度是 - 当前节点左子树的高度的>1
	public void LLrotate() {
		// 新节点的值放当前节点的值
		TreeNode NewRoot = new TreeNode(this.getData());
		// 新节点的左子树连当前节点的左子树
		NewRoot.leftNode = this.leftNode;
		// 新节点的右子树连当前节点的右子树的左子树
		NewRoot.rightNode = this.rightNode.leftNode;
		// 当前节点的值变为当前节点的右子树的值
		this.setData(this.rightNode.getData());
		// 当前节点的左子树的连新结点
		this.leftNode = NewRoot;
		// 当前节点的右子树连当前节点的右子树的右子树
		this.rightNode = this.rightNode.rightNode;
	}
	
	//先右旋再左旋---》当前节点右子树的左子树的高度 > 当前节点右子树的右子树的高度
//  ====》并且 当前节点的右子树的高度是 - 当前节点左子树的高度的>1
	public void RLrotate() {
		rightNode.RRrotate();//以当前节点的右节点为根节点 先进行右旋
		LLrotate();//当前节点进行左旋
		
	}
	

	// 获取以当前节点为根节点的右子树的高度
	public int GetRightHeight() {
		if (rightNode == null) {
			return 0;
		}
		return rightNode.height();
	}

	// 获取以当前节点为根节点的左子树的高度
	public int GetLeftHeight() {
		if (leftNode == null) {
			return 0;
		}
		return leftNode.height();
	}

	// 求高度
	public int height() {
		return Math.max(leftNode == null ? 0 : leftNode.height(), rightNode == null ? 0 : rightNode.height()) + 1;
	}

	// 添加
	public void add(TreeNode node) {
		// 小的在左，大的在右，相同的随便放
		if (this.data >= node.data) {
			// 要添加的结点应该放到左边
			if (this.leftNode != null) {
				this.leftNode.add(node);
			} else {
				this.leftNode = node;
			}
		} else {
			// 要添加的结点放到右边
			if (this.rightNode != null) {
				this.rightNode.add(node);
			} else {
				this.rightNode = node;
			}
		}
		
		//当一个结点添加完后，要判断左右子树的高度差是否>1
		if(this.GetLeftHeight()-this.GetRightHeight()>1) {
			//判断是要右旋还是先左旋再右旋
			if(this.leftNode!=null && this.leftNode.GetRightHeight()>this.leftNode.GetLeftHeight()) {
				//此时要先左旋再右旋
				LRrotate();
			}else {
				//说明左子树的左子树-左子树的右子树的高度>1,右旋
				RRrotate();
			}
		}else if(this.GetRightHeight()-this.GetLeftHeight()>1){
			//判断是要左旋还是先右旋再左旋
			if(rightNode!=null && rightNode.GetLeftHeight()>rightNode.GetRightHeight()) {
				//先右旋再左旋
				RLrotate();
			}else {
				////说明右子树的右子树-右子树的左子树的高度>1,直接左旋
				LLrotate();
			}
		}
		

	}

	// 构造器
	public TreeNode(int data) {
		this.data = data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public int getData() {
		return data;
	}

	public void setLeft(TreeNode leftNode) {
		this.leftNode = leftNode;
	}

	public TreeNode getLeft() {
		return leftNode;
	}

	public void setRight(TreeNode rightNode) {
		this.rightNode = rightNode;
	}

	public TreeNode getRight() {
		return rightNode;
	}

}